package question.solution363;

import question.SolutionTemplate;

import java.util.TreeSet;

public class Solution363 implements SolutionTemplate {

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        int ans = Integer.MIN_VALUE;
        for(int l=0;l<colLength;l++){
            int[] rowSum = new int[rowLength];
            for(int r=l;r<colLength;r++){
                for(int i=0;i<rowLength;i++){
                    rowSum[i]+=matrix[i][r];
                }
                TreeSet<Integer> sumSet = new TreeSet<Integer>();
                sumSet.add(0);
                int s = 0;
                for (int v : rowSum) {
                    s += v;
                    Integer ceil = sumSet.ceiling(s - k);
                    if (ceil != null) {
                        ans = Math.max(ans, s - ceil);
                    }
                    sumSet.add(s);
                }

            }
        }
        return ans;
    }

    public void test() {
//        char a ='9';
//        System.out.println(a-48);
        String str = "06";
//        int result = numDecodings(str);
        return;
    }
}
